

#动态规划算法
"""
1. dp数组的定义，以及下标的含义
2. 递推公式
3. dp数组如何初始化
4. 遍历顺序
5. 打印dp数组
"""

# 1.斐波那契数列：求第n个斐波那契数
""""
(1)dp[i]:第i个斐波那契数值为dp[i]
(2)递推公式：dp[i] = dp[i-1] + dp[i-2]
(3)如何初始化：dp[0] = 1, dp[1] = 1
(4)确定遍历顺序：从前往后遍历
(5)打印dp数组：用来debug
"""
def fibonacci(n):
    if n <= 0:
        return 0
    if n==1 or n==2:
        return 1
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    print(dp)
    return dp[n]

# 2.爬楼梯：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
"""
(1)dp[i]：达到第i阶，有dp[i]种方法
(2)递推公式：dp[i] = dp[i-1] + dp[i-2]
(3)如何初始化：dp[1] = 1; dp[2] = 2
(4)确定遍历顺序：从前往后
(5)打印dp数组
"""

def climbStairs(n):
    if n==1:
        return 1
    if n==2:
        return 2
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp)
    return dp[n]

# 3.使用最小花费爬楼梯：给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
# 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
# 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
# 请你计算并返回达到楼梯顶部的最低花费。
#
"""
(1)dp[i]：达到i层楼顶的最低花费为dp[i]
(2)递推公式：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + dp[i - 2])
(3)如何初始化：dp[0] = 0, dp[1] = 0
(4)确定遍历顺序：从前往后
(5)打印dp数组
"""
def climbStairs_cost(cost):
    n = len(cost)
    if n == 0:
        return 0
    if n == 1:
        return 0
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 0
    for i in range(2, n + 1):
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    return dp[n]

# 4.不同路径：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
# 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
# 问总共有多少条不同的路径？
"""
(1)dp[i][j]:从[0][0]到[i][j]有dp[i][j]条不同的路径
(2)递推公式：dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
(3)如何初始化：dp[0][j] = 1 ; dp[i][0] = 1
(4)确定遍历顺序:从左往右，从上往下
(5)打印dp
"""
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    # print(dp)
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    print(dp)
    return dp[m - 1][n - 1]

# 5.不同路径2：给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。
# 机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
# 网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
# 返回机器人能够到达右下角的不同路径数量
"""
(1)dp[i][j]：从[0][0]到[i][j]共有dp[i][j]条路径数量
(2)递推公式：
(3)如何初始化：
(4)遍历方向：
(5)打印dp
"""
def grid_unique_paths(grid):
    m = len(grid)
    n = len(grid[0])
    if grid[0][0] == 1 or grid[m - 1][n - 1] == 1:
        return 0
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    #初始化第一行
    for j in range(1, n):
        if grid[0][j] == 0 and dp[0][j - 1] == 1:
            dp[0][j] = 1
        else:
            dp[0][j] = 0
    for i in range(1, m):
        if grid[i][0] == 0 and dp[i - 1][0] == 1:
            dp[i][0] = 1
        else:
            dp[i][0] = 0
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
    return dp[m -1][n - 1]

# 6.整数拆分：给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
#返回 你可以获得的最大乘积
"""
(1)dp[i]:对i进行拆分，拆分后得到的最大的乘积为dp[i]
(2)递推公式：i : j, i-j; >=3: j*dp[i-j] --> dp[i] = j * dp[i - j]
(3)如何初始化：dp[2] = 1, dp[1] = 0
(4)遍历方向：i=3;i<=n;i++    j=i;j<i;j++
(5)打印dp数组：dp[n]
"""
#解题思路：i分为j和i-j；对于i-j有2个处理方式：
# ①不继续拆分，乘积为：j*(i-j);②继续拆分，j*dp[i-j]
def integerBreak(n):
    if n == 2:
        return 1
    dp = [0] * (n + 1)
    dp[2] = 1
    dp[1] = 0
    for i in range(3, n + 1):
        for j in range(1, i):
            dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
    return dp[n]









if __name__ == '__main__':
    # print(fibonacci(5))
    # print(climbStairs(5))
    # print(climbStairs_cost([10, 15, 20]))
    # print(unique_paths(3, 2))
    grid1 = [
        [0, 0, 0],
        [0, 1, 0],
        [0, 0, 0]
    ]
    print(grid_unique_paths(grid1))